신장 부분 그래프

3. 성질

임의의 그래프 $\backslash Gamma$의 신장 부분 그래프의 수는 $2^$

이다. (여기서 $\backslash operatorname\; E(\backslash Gamma)$는 $\backslash Gamma$의 간선 집합이다.) 모든 연결 그래프는 적어도 하나의 신장 나무를 갖는다. (무한 그래프의 경우 선택 공리가 필요하다.)^[27][28] 연결 그래프의 신장 트리는 순환 매트로이드의 기저와 같다.^[5]

4. 최소 비용 신장 트리 (Minimum Spanning Tree)

연결 유한 그래프 $\backslash Gamma$와 함수 $f\backslash colon\backslash operatorname\; E(\backslash Gamma)\backslash to\backslash mathbb\; R$ ('''비용 함수''', cost function^영어)가 주어졌을 때, $\backslash Gamma$의 '''최소 비용 신장 나무 부분 그래프'''(最小費用身長部分graph, minimum cost spanning tree^영어)는 $\backslash Gamma$의 연결 신장 부분 그래프 $\backslash Gamma\text{'}\backslash subseteq\backslash Gamma$ 가운데, 변들의 비용의 합

:$\backslash sum\_\{e\backslash in\backslash operatorname\; E(\backslash Gamma\text{'})\backslash subseteq\backslash operatorname\; E(\backslash Gamma)\}f(e)\backslash in\backslash mathbb\; R$

를 최소화하는 것이다. 이는 항상 나무 그래프가 되며, 항상 존재한다.

각 변에 가중치(비용)가 있는 경우, 최소 총합 비용으로 구성된 신장 트리를 '''최소 신장 트리'''라고 한다. 어떤 분야의 그래프 이론에서는 가중 그래프의 최소 신장 트리를 찾는 것이 종종 유용하다.

최소 신장 트리를 찾는 대표적인 알고리즘은 다음과 같다:

• 크루스칼 알고리즘: 단순한 탐욕법으로 계산량은 $O(E\; \backslash log\{E\})$이다.
• 프림 알고리즘: 탐욕법이지만 계산량은 $O(E\; +\; V\; \backslash log\{V\})$이다. 변의 수가 정점에 비해 충분히 클 때는 $O(E)$로 간주할 수 있다.

변의 가중치가 균일한 경우에는 너비 우선 탐색으로 $O(E)$에 구할 수 있다.

5. 최단 경로 트리 (Shortest Path Tree)

최단 경로 문제는 어떤 정점에서 다른 정점으로 가는 비용이 가장 적게 드는 경로를 찾는 문제이다. 어떤 정점에서 다른 모든 정점으로 이동하는 비용이 가장 적게 드는 트리를 '''최단 경로 트리'''라고 하며, 이는 신장 트리이다. 최단 경로 트리를 구하는 방법으로는 다익스트라 알고리즘, 벨만-포드 알고리즘 등이 있다.^[1]

6. 신장 트리 계산

케일리 공식에 따라, $K\_n$의 $2^\{n(n-1)/2\}$개의 신장 부분 그래프 가운데 $n^\{n-2\}$개가 신장 트리이다.

연결된 그래프의 스패닝 트리의 수 ''t''(''G'')는 잘 연구된 불변량이다. 특정 그래프의 경우, ''t''(''G'')는 다음과 같이 계산할 수 있다.

그래프	신장 트리 개수(t(G))
트리	1[12]
사이클 그래프 Cn	n[12]
완전 그래프 Kn	$n^\{n-2\}$ (케일리 공식)[12]
완전 이분 그래프 $K\_\{p,q\}$	$p^\{q-1\}q^\{p-1\}$[8]
n차원 하이퍼큐브 그래프 $Q\_n$	$2^\{2^n-n-1\}\backslash prod\_\{k=2\}^n\; k^$[13]

임의의 그래프 ''G''에 대해, 신장 트리의 수 ''t''(''G'')는 키르히호프의 행렬-나무 정리를 사용하여 다항 시간에 계산할 수 있다.^[14]

''t''(''G'')를 계산하는 방법은 다음과 같다.

1. 그래프의 라플라시안 행렬을 구성한다. 이는 행과 열이 모두 ''G''의 정점들로 인덱싱된 정사각 행렬이며, 행 ''i''와 열 ''j''의 항목은 다음 세 가지 값 중 하나이다.

• ''i'' = ''j''인 경우 정점 ''i''의 차수
• 정점 ''i''와 ''j''가 인접한 경우 -1
• 정점 ''i''와 ''j''가 서로 다르지만 인접하지 않은 경우 0

• ''e''는 ''G''의 임의의 모서리이다.
• ''G'' − ''e''는 ''e''를 삭제하여 얻은 멀티그래프이다.
• ''G''/''e''는 ''G''의 ''e''에 의한 모서리 축약이다.^[15]
• ''t''(''G'' − ''e'')는 모서리 ''e''를 사용하지 않는 ''G''의 신장 트리를 센다.
• ''t''(''G''/''e'')는 ''e''를 사용하는 ''G''의 신장 트리를 센다.

7. 알고리즘

유한 연결 그래프의 최소 비용 신장 부분 그래프는 프림 알고리즘이나 크러스컬 알고리즘을 사용하여 다항 시간 안에 찾을 수 있다. 그래프의 단일 신장 트리는 선형 시간 안에 깊이 우선 탐색 또는 너비 우선 탐색으로 찾을 수 있다. 이 두 알고리즘 모두 임의의 정점 ''v''에서 시작하여 발견한 정점의 이웃을 반복하고 탐색되지 않은 각 이웃을 나중에 탐색할 데이터 구조에 추가하여 주어진 그래프를 탐색한다. 이들은 이 데이터 구조가 스택 (깊이 우선 탐색의 경우)인지 큐 (너비 우선 탐색의 경우)인지에 따라 다르다. 어느 경우든, 루트 정점 ''v''를 제외한 각 정점을 발견된 정점에 연결하여 신장 트리를 형성할 수 있다. 이 트리는 이를 구성하는 데 사용된 그래프 탐색 알고리즘에 따라 깊이 우선 탐색 트리 또는 너비 우선 탐색 트리로 알려져 있다.^[18] 깊이 우선 탐색 트리는 19세기에 깊이 우선 탐색을 발견한 사람의 이름을 딴 트레모 트리라고 불리는 신장 트리의 특별한 경우이다.^[19]

신장 트리는 병렬 및 분산 컴퓨팅에서 프로세서 집합 간의 통신을 유지하는 방법으로 중요하다. 예를 들어 OSI 링크 계층 장치에서 사용되는 스패닝 트리 프로토콜 또는 분산 컴퓨팅을 위한 Shout (프로토콜)를 참조할 수 있다. 그러나 순차 컴퓨터에서 신장 트리를 구성하기 위한 깊이 우선 및 너비 우선 방법은 병렬 및 분산 컴퓨터에 적합하지 않다.^[20] 대신, 연구자들은 이러한 계산 모델에서 신장 트리를 찾기 위한 몇 가지 더 전문화된 알고리즘을 고안했다.^[21]

각 변에 가중치(비용)가 있는 경우, 최소 총합 비용으로 구성된 신장 트리를 '''최소 신장 트리'''라고 한다.

변의 가중치가 균일한 경우에는 너비 우선 탐색으로 $O(E)$에 구할 수 있다. 최단 경로 문제는 어떤 정점에서 다른 정점으로의 이동 비용이 최소가 되는 경로를 구하는 문제이다. 어떤 정점에서 다른 모든 정점으로 이동하는 비용이 최소가 되는 트리를 '''최단 경로 트리'''라고 하며, 이는 신장 트리이다. 최단 경로 문제는 단일 정점에서 임의의 정점으로의 최단 경로 트리를 구하는 방법으로는 다익스트라 알고리즘이나 벨만-포드 알고리즘 등이 있으며, 임의의 정점에서 임의의 정점으로의 이동 비용이 최소가 되는 최단 경로 트리를 구하는 방법으로는 플로이드-워셜 알고리즘이 알려져 있다.

8. 응용

경로 탐색 알고리즘, 다익스트라 알고리즘, A* 탐색 알고리즘 등은 문제를 해결하기 위한 중간 단계로 내부적으로 신장 트리를 구축한다.

전력 네트워크, 배선 연결, 배관, 자동 음성 인식 등 비용을 최소화하기 위해 최소 신장 트리를 찾는 과정에서 중간 단계로 신장 트리(또는 여러 개의 트리)를 점진적으로 구축하는 알고리즘을 사용한다.^[2]

인터넷 및 기타 통신망은 일부 루프를 포함하는 메시 토폴로지에서 노드를 연결하는 전송 링크를 가지고 있다. 브리지 루프 및 라우팅 루프를 방지하기 위해 스패닝 트리 프로토콜, OSPF, 링크 상태 라우팅 프로토콜, 증강 트리 기반 라우팅 등과 같은 라우팅 프로토콜은 각 라우터가 신장 트리를 기억하도록 요구한다.^[3]

Xuong 트리는 위상 기하학에서 최대 종수를 가진 그래프 임베딩을 찾기 위해 사용되는 특수한 종류의 신장 트리이다. Xuong 트리는 나머지 그래프에서 홀수 개의 간선을 가진 연결 요소의 수가 가능한 한 적도록 하는 신장 트리이다. Xuong 트리와 관련된 최대 종수 임베딩은 다항 시간 내에 찾을 수 있다.^[4]

전역 트리의 개념은 컴퓨터 네트워크 관련 분야에서 중요한 위치를 차지한다. 단말, 라우터, 스위칭 허브 등을 정점으로, 연결된 케이블을 변으로 간주하면 네트워크는 하나의 거대한 그래프가 되며, 전역 트리는 그 그래프에 대한 경로 구축 절차로 간주할 수 있다. OSPF, STP 등에서는 최단 경로 트리를 구성하여 통신 경로를 결정한다.

참조

_[1] 웹사이트 Tree https://networkx.org[...] 2021-12-10
_[2] 웹사이트 On the History of the Minimum Spanning Tree Problem http://www.math.ucsd[...] 1985
_[3] Youtube Folklore of Network Protocol Design https://www.youtube.[...] Microsoft Research 2022-05-13
_[4] 서적 Topics in topological graph theory Cambridge University Press, Cambridge
_[5] 문서 Kocay, Kreher, 2004
_[6] 문서 Kocay, Kreher, 2004
_[7] 서적 Matroid Theory https://books.google[...] Oxford University Press
_[8] 서적 Pearls in Graph Theory: A Comprehensive Introduction Courier Dover Publications
_[9] 서적 Combinatorics: Topics, Techniques, Algorithms https://books.google[...] Cambridge University Press
_[10] 서적 Modern Graph Theory https://books.google[...] Springer
_[11] 서적 Graph Theory and Its Applications https://books.google[...] CRC Press
_[12] 서적 Proofs from THE BOOK Springer-Verlag
_[13] 간행물 A survey of the theory of hypercube graphs
_[14] 서적 Graphs, Algorithms, and Optimization https://books.google[...] CRC Press
_[15] 문서 Kocay, Kreher, 2004
_[16] 문서 Bollobás, 1998
_[17] 간행물 Inapproximability of the Tutte polynomial
_[18] 서적 The Design and Analysis of Algorithms https://books.google[...] Springer
_[19] 서적 Graph theory (Cambridge, 1981) North-Holland
_[20] 간행물 Depth-first search is inherently sequential
_[21] 간행물 A distributed algorithm for minimum-weight spanning trees https://dl.acm.org/d[...]
_[22] 서적 Handbook of Computational Geometry Elsevier
_[23] 서적 Spanning Trees and Optimization Problems CRC Press
_[24] 간행물 Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996)
_[25] 간행물 On finding a minimum spanning tree in a network with random weights http://www.stats.ox.[...]
_[26] 간행물 Finding all spanning trees of directed and undirected graphs
_[27] 서적 Trees Springer
_[28] 서적 Horizons of combinatorics Springer
_[29] 저널 Sandpile groups and spanning trees of directed line graphs
_[30] 문서 3-正則平面グラフを用いた結び目の構成に関する定理 日本数学協会
_[31] 웹사이트 3-正則平面グラフを用いた結び目の構成に関する定理 https://researchmap.[...]
_[32] 저널 O jistém problému minimálním http://hdl.handle.ne[...] 1926
_[33] 저널 Příspěvek k řešení otázky ekonomické stavby elektrovodných sítí http://hdl.handle.ne[...] 1926-03-05
_[34] 저널 On the history of the minimum spanning tree problem http://www.math.ucsd[...] 1985-01